home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1993 / Internet Info CD-ROM (Walnut Creek) (1993).iso / inet / internet-drafts / draft-ietf-pppext-compression-01.txt < prev    next >
Text File  |  1993-10-26  |  34KB  |  1,097 lines
  1. Network Working Group                                             D Rand
  2. Internet Draft                                                    Novell
  3. Expires in six months                                       October 1993
  4.  
  5.  
  6.                The PPP Compression Control Protocol (CCP)
  7.                   draft-ieft-pppext-compression-01.txt
  8.  
  9.  
  10.  
  11. Status of this Memo
  12.  
  13.    This document is the product of the Point-to-Point Protocol Working
  14.    Group of the Internet Engineering Task Force (IETF).  Comments should
  15.    be submitted to the ietf-ppp@ucdavis.edu mailing list.
  16.  
  17.    Distribution of this memo is unlimited.
  18.  
  19.    This document is an Internet Draft.  Internet Drafts are working
  20.    documents of the Internet Engineering Task Force (IETF), its Areas,
  21.    and its Working Groups.  Note that other groups may also distribute
  22.    working documents as Internet Drafts.
  23.  
  24.    Internet Drafts are draft documents valid for a maximum of six
  25.    months.  Internet Drafts may be updated, replaced, or obsoleted by
  26.    other documents at any time.  It is not appropriate to use Internet
  27.    Drafts as reference material or to cite them other than as a
  28.    ``working draft'' or ``work in progress.''
  29.  
  30.    Please check the 1id-abstracts.txt listing contained in the
  31.    internet-drafts Shadow Directories on nic.ddn.mil, nnsc.nsf.net,
  32.    nic.nordu.net, ftp.nisc.sri.com, or munnari.oz.au to learn the
  33.    current status of any Internet Draft.
  34.  
  35. Abstract
  36.  
  37.    The Point-to-Point Protocol (PPP) [1] provides a standard method of
  38.    encapsulating multiple protocol datagrams over point-to-point links.
  39.    PPP also defines an extensible Link Control Protocol.
  40.  
  41.    This document defines a method for negotiating data compression over
  42.    PPP links, and describes the use of several such data compression
  43.    protocols.
  44.  
  45.  
  46.  
  47.  
  48.  
  49.  
  50.  
  51.  
  52. Dave Rand                expires in six months                  [Page i]
  53. DRAFT                       PPP Compression                 October 1993
  54.  
  55.  
  56. 1.  Introduction
  57.  
  58.    PPP has three main components:
  59.  
  60.       1. A method for encapsulating datagrams over serial links.
  61.  
  62.       2. A Link Control Protocol (LCP) for establishing, configuring,
  63.          and testing the data-link connection.
  64.  
  65.       3. A family of Network Control Protocols (NCPs) for establishing
  66.          and configuring different network-layer protocols.
  67.  
  68.    In order to establish communications over a point-to-point link, each
  69.    end of the PPP link must first send LCP packets to configure and test
  70.    the data link.  After the link has been established and optional
  71.    facilities have been negotiated as needed by the LCP, PPP must send
  72.    NCP packets to choose and configure one or more network-layer
  73.    protocols.  Once each of the chosen network-layer protocols has been
  74.    configured, datagrams from each network-layer protocol can be sent
  75.    over the link.
  76.  
  77.    The link will remain configured for communications until explicit LCP
  78.    or NCP packets close the link down, or until some external event
  79.    occurs (an inactivity timer expires or network administrator
  80.    intervention).
  81.  
  82.  
  83.  
  84.  
  85.  
  86.  
  87.  
  88.  
  89.  
  90.  
  91.  
  92.  
  93.  
  94.  
  95.  
  96.  
  97.  
  98.  
  99.  
  100.  
  101.  
  102.  
  103.  
  104.  
  105.  
  106.  
  107. Dave Rand                expires in six months                  [Page 1]
  108. DRAFT                       PPP Compression                 October 1993
  109.  
  110.  
  111. 2.  A PPP Control Protocol (NCP) for Compression
  112.  
  113.    The Compression Control Protocol (CCP) is responsible for
  114.    configuring, enabling, and disabling data compression algorithms on
  115.    both ends of the point-to-point link.  It is also used to signal a
  116.    failure of the compression/decompression mechanism in a reliable
  117.    manner.  CCP uses the same packet exchange mechanism as the Link
  118.    Control Protocol (LCP).  CCP packets may not be exchanged until PPP
  119.    has reached the Network-Layer Protocol phase.  CCP packets received
  120.    before this phase is reached should be silently discarded.
  121.  
  122.    The Compression Control Protocol is exactly the same as the Link
  123.    Control Protocol [1] with the following exceptions:
  124.  
  125.    Data Link Layer Protocol Field
  126.  
  127.       Exactly one CCP packet is encapsulated in the Information field of
  128.       PPP Data Link Layer frames where the Protocol field indicates type
  129.       hex <TBD> (0xFD) (Compression Control Protocol).
  130.  
  131.    Code field
  132.  
  133.       Only Codes 1 through 7 (Configure-Request, Configure-Ack,
  134.       Configure-Nak, Configure-Reject, Terminate-Request, Terminate-Ack
  135.       and Code-Reject) are used.  Other Codes should be treated as
  136.       unrecognized and should result in Code-Rejects.
  137.  
  138.    Timeouts
  139.  
  140.       CCP packets may not be exchanged until PPP has reached the
  141.       Network-Layer Protocol phase.  An implementation should be
  142.       prepared to wait for Authentication and Link Quality Determination
  143.       to finish before timing out waiting for a Configure-Ack or other
  144.       response.  It is suggested that an implementation give up only
  145.       after user intervention or a configurable amount of time.
  146.  
  147.    Configuration Option Types
  148.  
  149.       CCP has a distinct set of Configuration Options, which are defined
  150.       below.
  151.  
  152. 2.1.  Sending Compressed Datagrams
  153.  
  154.    Before any compressed packets may be communicated, PPP must reach the
  155.    Network-Layer Protocol phase, and the Compression Control Protocol
  156.    must reach the Opened state.
  157.  
  158.    One or more compressed packets are encapsulated in the Information
  159.  
  160.  
  161.  
  162. Dave Rand                expires in six months                  [Page 2]
  163. DRAFT                       PPP Compression                 October 1993
  164.  
  165.  
  166.    field of PPP Data Link Layer frames.  Each of the compression types
  167.    may use a different mechanism to indicate the inclusion of more than
  168.    one uncompressed frame in a single PPP Data Link Layer frame.  The
  169.    Protocol Identifier of the compressed datagram indicates that the
  170.    frame is compressed, but not the algorithm with which it was
  171.    compressed.  Only one algorithm may be in use at time, and that is
  172.    negotiated prior to the first compressed frame being transmitted.
  173.  
  174.    The maximum length of a compressed packet transmitted over a PPP link
  175.    is the same as the maximum length of the Information field of a PPP
  176.    data link layer frame.  Larger datagrams (presumably the result of
  177.    the compression algorithm increasing the size of the message in some
  178.    cases) may be sent uncompressed, using its standard form, or may be
  179.    sent in multiple datagrams, if the compression algorithm supports it.
  180.  
  181.  
  182.  
  183.  
  184.  
  185.  
  186.  
  187.  
  188.  
  189.  
  190.  
  191.  
  192.  
  193.  
  194.  
  195.  
  196.  
  197.  
  198.  
  199.  
  200.  
  201.  
  202.  
  203.  
  204.  
  205.  
  206.  
  207.  
  208.  
  209.  
  210.  
  211.  
  212.  
  213.  
  214.  
  215.  
  216.  
  217. Dave Rand                expires in six months                  [Page 3]
  218. DRAFT                       PPP Compression                 October 1993
  219.  
  220.  
  221. 3.  CCP Configuration Options
  222.  
  223. CCP Configuration Options allow negotiation of compression algorithms
  224. and their parameters.  CCP uses the same Configuration Option format
  225. defined for LCP [1], with a separate set of Options.
  226.  
  227. Configuration Options, in this protocol, indicate algorithms that the
  228. receiver is willing or able to use to decompress data sent by the
  229. sender.  As a result, it is to be expected that systems will offer to
  230. accept several differing sets of algorithms, and negotiate down to one
  231. that will indeed be used.
  232.  
  233. There is the possibility of not being able to agree on a compression
  234. algorithm.  In that case, no compression will be used, and the link will
  235. come up without compression.  If LAPB has been separately negotiated,
  236. then LAPB will be used (unless it is re-negotiated off).
  237.  
  238. We expect many vendors to want to use proprietary compression
  239. algorithms, and have made a mechanism available to negotiate these
  240. without encumbering the Internet Assigned Number Authority with
  241. proprietary number requests.
  242.  
  243. If none of the protocols are not recognized, a Configure-Reject MAY be
  244. sent with the entire, unmodified Configure-Request.  The original
  245. transmitter of the Configure-Request, which was hoping to negotiate a
  246. compression of future network data packets sent to it, SHOULD interpret
  247. such a Configure-Reject as indicating that none of the proposed
  248. compression protocols are possible.
  249.  
  250. If any of the protocols are recognized but not acceptable due to local
  251. options in the request (or optional parameters not in the request), a
  252. Configure-NAK MUST be sent with the local options modified
  253. appropriately.  The Configure-NAK SHOULD contain only those protocols
  254. that might be acceptable.  Other protocols which are unacceptable,
  255. whether because unrecognized or for other reasons, MUST NOT be listed in
  256. the option in the Configure-NAK.  A new Configure-Request MAY then be
  257. sent with the options adjusted as specified in the Configure-Nak.
  258.  
  259.  
  260. The most up-to-date values of the CCP Option Type field are specified in
  261. the most recent "Assigned Numbers" RFC [6].  Current values are assigned
  262. as follows:
  263.  
  264.    CCP Option      Meaning
  265.    1       Compression type negotiation (common)
  266.    2       Compression type negotiation (OUI/proprietary)
  267.  
  268.  
  269.  
  270.  
  271.  
  272. Dave Rand                expires in six months                  [Page 4]
  273. DRAFT                       PPP Compression                 October 1993
  274.  
  275.  
  276. 3.1.  Compression Type Negotiation Option (common)
  277.  
  278.    Description
  279.  
  280.       This Configuration Option provides a way to negotiate the use of a
  281.       standard compression algorithm.  As of this writing, several
  282.       compression algorithms are specified (see appendix). By default,
  283.       compression is not enabled.
  284.  
  285.  
  286.     0                   1                   2                   3
  287.     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  288.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  289.    |     Type      |          Length               | Comp. Types   |
  290.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  291.    |  Length       | options...
  292.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  293.  
  294.    Type
  295.  
  296.       1
  297.  
  298.    Length
  299.  
  300.       >= 3
  301.  
  302.    Comp. Types (Compression Types)
  303.  
  304.       The compression types field lists the common compression
  305.       algorithms that the are available.  They must be listed in the
  306.       order of desirability for this particular link.  Each compression
  307.       type is followed with a length, which may be 0.  The length
  308.       indicates the number of octets of compression-specific negotiation
  309.       information, which may include items such as dictionary size,
  310.       maximum string length and number of dictionaries.
  311.  
  312.       The receiver will process the compression types field from left to
  313.       right, selecting the first protocol that matches the receiver's
  314.       capability.  If an acceptable compression protocol with acceptable
  315.       options is encountered, the Configure-Request MUST be ACK'ed.  The
  316.       ACK MUST list only this acceptable protocol
  317.  
  318.       If no completely acceptable protocol is found, but one or more
  319.       protocols are understood, but some or all of the compression
  320.       negotiation options are not acceptable, these may be modified and
  321.       sent back in a Configure-Nak.
  322.  
  323.       If none of the protocols are understood or no acceptable alternate
  324.  
  325.  
  326.  
  327. Dave Rand                expires in six months                  [Page 5]
  328. DRAFT                       PPP Compression                 October 1993
  329.  
  330.  
  331.       compression negotiation options are possible, a Configure-Reject
  332.       MUST be transmitted.  This Configure-Reject MUST be identical to
  333.       the original Configure-Request as required by PPP protocols.
  334.  
  335.       Implementation of any particular compression algorithm IS NOT
  336.       guaranteed.  If all protocols the sender implements are
  337.       Configure-Rejected by the receiver, then no compression is
  338.       enabled.
  339.  
  340.    Default
  341.  
  342.       No compression protocol enabled.
  343.  
  344.  
  345.  
  346.  
  347.  
  348.  
  349.  
  350.  
  351.  
  352.  
  353.  
  354.  
  355.  
  356.  
  357.  
  358.  
  359.  
  360.  
  361.  
  362.  
  363.  
  364.  
  365.  
  366.  
  367.  
  368.  
  369.  
  370.  
  371.  
  372.  
  373.  
  374.  
  375.  
  376.  
  377.  
  378.  
  379.  
  380.  
  381.  
  382. Dave Rand                expires in six months                  [Page 6]
  383. DRAFT                       PPP Compression                 October 1993
  384.  
  385.  
  386. 3.2.  Compression Type Negotiation Option (OUI/Proprietary)
  387.  
  388.    Description
  389.  
  390.       This Configuration Option provides a way to negotiate the use of a
  391.       proprietary compression protocol.  By default, such compression is
  392.       not enabled.  Since the first matching compression will be used,
  393.       it is recommended that any known OUI compression options be
  394.       transmitted first, before the common options are used.  Before
  395.       accepting this option, the implementation must verify that the
  396.       Organizationally Unique Identifier identifies a proprietary
  397.       algorithm that the implementation can decompress, and that any
  398.       vendor specific negotiation options are fully understood.  If no
  399.       OUIs are supported by an implementation, a Configure-Reject may be
  400.       sent back for any type 2 Compression Type Negotiation Option.
  401.  
  402.    A summary of the Proprietary Compression Algorithm Configuration
  403.    Option format is shown below.  The fields are transmitted from left
  404.    to right.
  405.  
  406.     0                   1                   2                   3
  407.     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  408.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  409.    |     Type      |          Length               | OUI MS octet  |
  410.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  411.    |     OUI remaining octects     |  Length       | options...
  412.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  413.  
  414.    Type
  415.  
  416.       2
  417.  
  418.    Length
  419.  
  420.       >= 3
  421.  
  422.    IEEE OUI
  423.  
  424.       The vendor's IEEE Organizationally Unique Identifier (OUI), which
  425.       is the most significant three octets of an Ethernet Physical
  426.       Address, assigned to the vendor by IEEE 802.  This identifies the
  427.       option as being proprietary to the indicated vendor.
  428.  
  429.       Multiple proprietary compression types may be offered, each with a
  430.       different OUI, by sending them out after a REJect for any previous
  431.       OUI has been received by the sender.  When a supported vendor-
  432.       specific proprietary compression is seen, and the option field is
  433.       valid, a Configure-Ack may be sent to indicate acceptance of this
  434.  
  435.  
  436.  
  437. Dave Rand                expires in six months                  [Page 7]
  438. DRAFT                       PPP Compression                 October 1993
  439.  
  440.  
  441.       compression type.
  442.  
  443.       Multiple vendor-specific proprietary compression types may be
  444.       implemented by the option field, which may contain algorithm
  445.       selection information, negotiated options such as dictionary size,
  446.       or any other information required.  If the information in the
  447.       option field is unrecognized, a Configure-Reject MUST be sent.  If
  448.       the information in the option field is recognized, but certain
  449.       value(s) are unavailable, a Configure-Nak MAY be sent with the
  450.       appropriate values modified.
  451.  
  452.       Any unrecognized proprietary compression configure request MUST
  453.       have a Configure-Reject sent back.
  454.  
  455.    Length
  456.  
  457.       The Length field specifies the number of octects of OUI-specific
  458.       negotiation information, in free format.  It may be followed by 0
  459.       to 255 octets of negotiation information.
  460.  
  461.  
  462.    options
  463.  
  464.       The options field is zero or more octets and contains additional
  465.       data as determined by the vendor's compression protocol.
  466.  
  467.    Default
  468.  
  469.       No proprietary compression protocol enabled.
  470.  
  471.  
  472.  
  473.  
  474.  
  475.  
  476.  
  477.  
  478.  
  479.  
  480.  
  481.  
  482.  
  483.  
  484.  
  485.  
  486.  
  487.  
  488.  
  489.  
  490.  
  491.  
  492. Dave Rand                expires in six months                  [Page 8]
  493. DRAFT                       PPP Compression                 October 1993
  494.  
  495.  
  496. A.  Common compression number identification
  497.  
  498.    The following numbers for common compression option use have been
  499.    defined.
  500.  
  501.       Compression ID  Algorithm specified
  502.       1               Predictor type 1
  503.       2               Predictor type 2
  504.       3               Puddle Jumper
  505.       16              Hewlett-Packard PPC
  506.       17              Stac Electronics LZS
  507.       18              Microsoft PPC
  508.       19              Gandalf FZA
  509.       20              V.42bis compression
  510.       21              UNIX LZW Compress
  511.  
  512.       IDs 4-15 are reserved for other freely-available implementations
  513.       of compression algorithms.
  514.  
  515.  
  516.  
  517.  
  518.  
  519.  
  520.  
  521.  
  522.  
  523.  
  524.  
  525.  
  526.  
  527.  
  528.  
  529.  
  530.  
  531.  
  532.  
  533.  
  534.  
  535.  
  536.  
  537.  
  538.  
  539.  
  540.  
  541.  
  542.  
  543.  
  544.  
  545.  
  546.  
  547. Dave Rand                expires in six months                  [Page 9]
  548. DRAFT                       PPP Compression                 October 1993
  549.  
  550.  
  551. B.  Common compression algorithm definitions
  552.  
  553.    A compression algorithm that is available without license fees is the
  554.    predictor algorithm, defined below.  Note that although care has been
  555.    taken to ensure that the following code does not infringe any
  556.    patents, there is no assurance that it is not covered by a patent.
  557.    Use the following code at your own risk.
  558.  
  559.    B.1.  Predictor algorithm
  560.  
  561.       Predictor works by filling a guess table with values, based on the
  562.       hash of the previous characters seen. Since we are either emitting
  563.       the source data, or depending on the guess table, we add a flag
  564.       bit for every byte of input, telling the decompressor if it should
  565.       retrieve the byte from the compressed data stream, or the guess
  566.       table. Blocking the input into groups of 8 characters means that
  567.       we don't have to bit-insert the compressed output - a flag byte
  568.       preceeds every 8 bytes of compressed data. Each bit of the flag
  569.       byte corresponds to one byte of reconstructed data.
  570.  
  571.       Take the source file:
  572.  
  573.       000000    4141 4141 4141 410a  4141 4141 4141 410a    AAAAAAA.AAAAAAA.
  574.       000010    4141 4141 4141 410a  4141 4141 4141 410a    AAAAAAA.AAAAAAA.
  575.       000020    4142 4142 4142 410a  4241 4241 4241 420a    ABABABA.BABABAB.
  576.       000030    7878 7878 7878 780a                         xxxxxxx.
  577.  
  578.       Compressing the above data yields the following:
  579.  
  580.       000000    6041 4141 4141 0a60  4141 4141 410a 6f41    `AAAAA.`AAAAA.oA
  581.       000010    0a6f 410a 4142 4142  4142 0a60 4241 4241    .oA.ABABAB.`BABA
  582.       000020    420a 6078 7878 7878  0a                     B.`xxxxx.
  583.  
  584.       Reading the above data says:
  585.       flag = 0x60 - 2 bytes in this block were guessed correctly, 5 and 6.
  586.            Reconstructed data is:    0 1 2 3 4 5 6 7
  587.               File:                  A A A A A
  588.               Guess table:                     A A
  589.       flag = 0x60 - 2 bytes in this block were guessed correctly, 5 and 6.
  590.            Reconstructed data is:    0 1 2 3 4 5 6 7
  591.               File:                  A A A A A
  592.               Guess table:                     A A
  593.       flag = 0x6f - 6 bytes in this block were guessed correctly, 0-3, 5 and 6.
  594.            Reconstructed data is:    0 1 2 3 4 5 6 7
  595.               File:                          A
  596.               Guess table:           A A A A   A A
  597.       flag = 0x6f - 6 bytes in this block were guessed correctly, 0-3, 5 and 6.
  598.            Reconstructed data is:    0 1 2 3 4 5 6 7
  599.  
  600.  
  601.  
  602. Dave Rand                expires in six months                 [Page 10]
  603. DRAFT                       PPP Compression                 October 1993
  604.  
  605.  
  606.               File:                          A
  607.               Guess table:           A A A A   A A
  608.       flag = 0x41 - 2 bytes in this block were guessed correctly, 0 and 6.
  609.            Reconstructed data is:    0 1 2 3 4 5 6 7
  610.               File:                    B A B A B
  611.               Guess table:           A           A
  612.       flag = 0x60 - 2 bytes in this block were guessed correctly, 5 and 6.
  613.            Reconstructed data is:    0 1 2 3 4 5 6 7
  614.               File:                  B A B A B
  615.               Guess table:                     A B
  616.       flag = 0x60 - 2 bytes in this block were guessed correctly, 5 and 6
  617.            Reconstructed data is:    0 1 2 3 4 5 6 7
  618.               File:                  x x x x x
  619.               Guess table:                     x x
  620.  
  621.       And now, on to the source - note that it has been modified to work
  622.       with a split block. If your data stream can't be split within a
  623.       block (eg, compressing packets), then the code dealing with
  624.       "final", and the memcpy are not required.  You can detect this
  625.       situation (or errors, for that matter) by observing that the flag
  626.       byte indicates that more data is required from the compressed data
  627.       stream, but you are out of data (len in decompress is <= 0). It
  628.       *is* ok if len == 0, and flags indicate guess table usage.
  629.  
  630.       #include <stdio.h>
  631.       #ifdef __STDC__
  632.       #include <stdlib.h>
  633.       #endif
  634.       #include <string.h>
  635.       /*
  636.        * pred.c -- Test program for Dave Rand's rendition of the
  637.        * predictor algorithm
  638.        * Updated by: iand@labtam.labtam.oz.au (Ian Donaldson)
  639.        * Updated by: Carsten Bormann <cabo@cs.tu-berlin.de>
  640.        * Original  : Dave Rand <dlr@bungi.com>/<dave_rand@novell.com>
  641.        */
  642.  
  643.       /* The following hash code is the heart of the algorithm:
  644.        * It builds a sliding hash sum of the previous 3-and-a-bit characters
  645.        * which will be used to index the guess table.
  646.        * A better hash function would result in additional compression,
  647.        * at the expense of time.
  648.        */
  649.       #define HASH(x) Hash = (Hash << 4) ^ (x)
  650.  
  651.       static unsigned short int Hash;
  652.       static unsigned char GuessTable[65536];
  653.  
  654.  
  655.  
  656.  
  657. Dave Rand                expires in six months                 [Page 11]
  658. DRAFT                       PPP Compression                 October 1993
  659.  
  660.  
  661.       static int
  662.       compress(source, dest, len)
  663.       unsigned char *source, *dest;
  664.       int len;
  665.       {
  666.           int i, bitmask;
  667.           unsigned char *flagdest, flags, *orgdest;
  668.  
  669.           orgdest = dest;
  670.           while (len) {
  671.               flagdest = dest++; flags = 0;   /* All guess wrong initially */
  672.               for (bitmask=1, i=0; i < 8 && len; i++, bitmask <<= 1) {
  673.                   if (GuessTable[Hash] == *source) {
  674.                       flags |= bitmask;       /* Guess was right - don't output */
  675.                   } else {
  676.                       GuessTable[Hash] = *source;
  677.                       *dest++ = *source;      /* Guess wrong, output char */
  678.                   }
  679.                   HASH(*source++);len--;
  680.               }
  681.               *flagdest = flags;
  682.           }
  683.           return(dest - orgdest);
  684.       }
  685.  
  686.       static int
  687.       decompress(source, dest, lenp, final)
  688.       unsigned char *source, *dest;
  689.       int *lenp, final;
  690.       {
  691.           int i, bitmask;
  692.           unsigned char flags, *orgdest;
  693.           int len = *lenp;
  694.  
  695.           orgdest = dest;
  696.           while (len >= 9) {
  697.               flags = *source++;
  698.               for (i=0, bitmask = 1; i < 8; i++, bitmask <<= 1) {
  699.                   if (flags & bitmask) {
  700.                       *dest = GuessTable[Hash];       /* Guess correct */
  701.                   } else {
  702.                       GuessTable[Hash] = *source;     /* Guess wrong */
  703.                       *dest = *source++;              /* Read from source */
  704.                       len--;
  705.                   }
  706.                   HASH(*dest++);
  707.               }
  708.               len--;
  709.  
  710.  
  711.  
  712. Dave Rand                expires in six months                 [Page 12]
  713. DRAFT                       PPP Compression                 October 1993
  714.  
  715.  
  716.           }
  717.           while (final && len) {
  718.               flags = *source++;
  719.               len--;
  720.               for (i=0, bitmask = 1; i < 8; i++, bitmask <<= 1) {
  721.                   if (flags & bitmask) {
  722.                       *dest = GuessTable[Hash];       /* Guess correct */
  723.                   } else {
  724.                       if (!len)
  725.                           break;      /* we seem to be really done -- cabo */
  726.                       GuessTable[Hash] = *source;     /* Guess wrong */
  727.                       *dest = *source++;              /* Read from source */
  728.                       len--;
  729.                   }
  730.                   HASH(*dest++);
  731.               }
  732.           }
  733.           *lenp = len;
  734.           return(dest - orgdest);
  735.       }
  736.  
  737.       #define SIZ1 8192
  738.  
  739.       static void
  740.       compress_file(f) FILE *f; {
  741.           char bufp[SIZ1];
  742.           char bufc[SIZ1/8*9+9];
  743.           int len1, len2;
  744.           while ((len1 = fread(bufp, 1, SIZ1, f)) > 0) {
  745.               len2 = compress((unsigned char *)bufp, (unsigned char *)bufc, len1);
  746.               (void) fwrite(bufc, 1, len2, stdout);
  747.           }
  748.       }
  749.  
  750.       static void
  751.       decompress_file(f) FILE *f; {
  752.           char bufp[SIZ1+9];
  753.           char bufc[SIZ1*9+9];
  754.           int len1, len2, len3;
  755.  
  756.           len1 = 0;
  757.           while ((len3 = fread(bufp+len1, 1, SIZ1, f)) > 0) {
  758.               len1 += len3;
  759.               len3 = len1;
  760.               len2 = decompress((unsigned char *)bufp, (unsigned char *)bufc, &len1, 0);
  761.               (void) fwrite(bufc, 1, len2, stdout);
  762.               (void) memcpy(bufp, bufp+len3-len1, len1);
  763.           }
  764.  
  765.  
  766.  
  767. Dave Rand                expires in six months                 [Page 13]
  768. DRAFT                       PPP Compression                 October 1993
  769.  
  770.  
  771.           len2 = decompress((unsigned char *)bufp, (unsigned char *)bufc, &len1, 1);
  772.           (void) fwrite(bufc, 1, len2, stdout);
  773.       }
  774.  
  775.       int
  776.       main(ac, av)
  777.           int ac;
  778.           char** av;
  779.       {
  780.           char **p = av+1;
  781.           int dflag = 0;
  782.  
  783.           for (; --ac > 0; p++) {
  784.               if (!strcmp(*p, "-d"))
  785.                   dflag = 1;
  786.               else if (!strcmp(*p, "-"))
  787.                   (dflag?decompress_file:compress_file)(stdin);
  788.               else {
  789.                   FILE *f = fopen(*p, "r");
  790.                   if (!f) {
  791.                       perror(*p);
  792.                       exit(1);
  793.                   }
  794.                   (dflag?decompress_file:compress_file)(f);
  795.                   (void) fclose(f);
  796.               }
  797.           }
  798.           return(0);
  799.       }
  800.  
  801.    B.2.  Encapsulation for Predictor type 1
  802.       The correct encapsulation for type 1 compression is the protocol
  803.       type, 1 bit indicating if the data is compressed or not, 15 bits
  804.       of the uncompressed data length in octets, compressed data, and
  805.       uncompressed CRC-16 of the two octets of unsigned length in
  806.       network byte order, followed by the original, uncompressed data
  807.       packet.
  808.  
  809.        0                   1
  810.        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
  811.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  812.       | CCP Protocol Identifier       |
  813.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  814.       |*| Uncompressed length (octets)|   * is compressed flag
  815.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   1 means data is compressed
  816.       | Compressed data...            |   0 means data is not compressed
  817.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  818.       | CRC - 16                      |
  819.  
  820.  
  821.  
  822. Dave Rand                expires in six months                 [Page 14]
  823. DRAFT                       PPP Compression                 October 1993
  824.  
  825.  
  826.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  827.  
  828.       The CCP Protocol Identifier that starts the packet is always 0xfd.
  829.       If PPP Protocol field compression has not be negotiated, it MUST
  830.       be a 16-bit field.
  831.  
  832.       The Compressed data is the Protocol Identifier and the Info fields
  833.       of the original PPP packet described in [1], but not the Address,
  834.       Control, FCS, or Flag.  The CCP Protocol field MAY be compressed
  835.       as described in [1], regardless of whether the Protocol field of
  836.       the CCP Protocol Identifier is compressed or whether PPP Protocol
  837.       field compression has been negotiated.
  838.  
  839.       It is not required that any of the fields land on an even word
  840.       boundary - the compressed data may be of any length.  If during
  841.       the decode procedure, the CRC-16 does not match the decoded frame,
  842.       it means that the compress or decompress process has become
  843.       desyncronized.  This will happen as a result of a frame being lost
  844.       in transit if LAPB is not used.  In this case, a new configure-
  845.       request must be sent, and the CCP will drop out of the open state.
  846.       Upon receipt of the configure-ack, the predictor tables are
  847.       cleared to zero, and compression can be resumed without data loss.
  848.  
  849.    B.3.  Encapsulation for Predictor type 2
  850.       The correct encapsulation for type 2 compression is the protocol
  851.       type, followed by the data stream.  Within the data stream is the
  852.       current frame length (uncompressed), compressed data, and
  853.       uncompressed CRC-16 of the two octets of unsigned length in
  854.       network byte order, followed by the original, uncompressed data.
  855.       The data stream may be broken at any convenient place for
  856.       encapsulation purposes.  With type 2 encapsulation, LAPB is almost
  857.       essential for correct delivery.
  858.  
  859.        0                   1
  860.        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
  861.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  862.       | CCP Protocol Identifier       |
  863.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  864.       |*| Uncompressed length (octets)|   * is compressed flag
  865.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   1 means data is compressed
  866.       | Compressed data...            |   0 means data is not compressed
  867.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  868.       | CRC-16                        |
  869.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  870.       |*| Uncompressed length (octets)|   * is compressed flag
  871.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  872.                ...
  873.  
  874.  
  875.  
  876.  
  877. Dave Rand                expires in six months                 [Page 15]
  878. DRAFT                       PPP Compression                 October 1993
  879.  
  880.  
  881.       The CCP Protocol Identifier that starts the packet is always 0xfd.
  882.       If PPP Protocol field compression has not be negotiated, it MUST
  883.       be a 16-bit field.
  884.  
  885.       The Compressed data is the Protocol Identifier and the Info fields
  886.       of the original PPP packet described in [1], but not the Address,
  887.       Control, FCS, or Flag.  The CCP Protocol field MAY be compressed
  888.       as described in [1], regardless of whether the Protocol field of
  889.       the CCP Protocol Identifier is compressed or whether PPP Protocol
  890.       field compression
  891.  
  892.       It is not required that any field land on an even word boundary -
  893.       the compressed data may be of any length.  If during the decode
  894.       procedure, the CRC-16 does not match the decoded frame, it means
  895.       that the compress or decompress process has become desyncronized.
  896.       This will happen as a result of a frame being lost in transit if
  897.       LAPB is not used.  In this case, a new configure-request must be
  898.       sent, and the CCP will drop out of the open state.  Upon receipt
  899.       of the configure-ack, the predictor tables are cleared to zero,
  900.       and compression can be resumed without data loss.
  901.  
  902.    C.  CCP Recommended Options
  903.  
  904.       The following Configurations Options are recommended:
  905.  
  906.          IP-Compression-Protocol -- with at least 4 slots, usually 16
  907.          slots.
  908.  
  909.          IP-Address -- only on dial-up lines.
  910.  
  911.  
  912.    Security Considerations
  913.  
  914.       Security issues are not discussed in this memo.
  915.  
  916.  
  917. References
  918.  
  919.    [1]   Simpson, W. A., "The Point-to-Point Protocol", RFC in progress.
  920.  
  921.    [2]   Postel, J., "Internet Protocol", RFC 791, USC/Information
  922.          Sciences Institute, September 1981.
  923.  
  924.    [3]   Jacobson, V., "Compressing TCP/IP Headers", RFC 1144, January
  925.          1990.
  926.  
  927.    [4]   Postel, J., "The TCP Maximum Segment Size Option and Related
  928.          Topics", RFC 879, USC/Information Sciences Institute, November
  929.  
  930.  
  931.  
  932. Dave Rand                expires in six months                 [Page 16]
  933. DRAFT                       PPP Compression                 October 1993
  934.  
  935.  
  936.          1983.
  937.  
  938.    [5]   Reynolds, J., Postel,J., "Assigned Numbers", RFC 1340,
  939.          USC/Information Sciences Institute, March 1990.
  940.  
  941.    [6]   Perkins, D., Hobby, R., "Point-to-Point Protocol (PPP) initial
  942.          configuration options", RFC 1172, August 1990.
  943.  
  944.    [7]   Carr, D., "PPP Gandalf FZA Compression Protocol", Work in
  945.          progress.
  946.  
  947.    [8]   Lutz, R., "PPP Stacker LZS Compression Protocol", Work in
  948.          progress.
  949.  
  950.    [9]   Simpson, W.A., "PPP Puddle Jumper Compression Protocol", Work
  951.          in progress.
  952.  
  953.    [10]  Dimitri, T.J., "PPP Microsoft LZ Compression Protocol", Work in
  954.          progress.
  955.  
  956.  
  957.  
  958. Acknowledgments
  959.  
  960.    Some of the text in this document is taken from RFCs 1171 & 1172, by
  961.    Drew Perkins of Carnegie Mellon University, and by Russ Hobby of the
  962.    University of California at Davis.
  963.  
  964.    Information leading to the expanded IP-Compression option provided by
  965.    Van Jacobson at SIGCOMM '90.
  966.  
  967.    The predictor algorithm was originally implemented by Timo Raita, at
  968.    the ACM SIG Conference, New Orleans, 1987.
  969.  
  970.    Bill Simpson helped with the document formatting.
  971.  
  972.  
  973. Chair's Address
  974.  
  975.    The working group can be contacted via the current chair:
  976.  
  977.       Fred Baker
  978.       Advanced Computer Communications
  979.       315 Bollay Drive
  980.       Santa Barbara, California 93117
  981.  
  982.       (805) 685 4455
  983.  
  984.  
  985.  
  986.  
  987. Dave Rand                expires in six months                 [Page 17]
  988. DRAFT                       PPP Compression                 October 1993
  989.  
  990.  
  991.       EMail: fbaker@acc.com
  992.  
  993.  
  994.  
  995. Author's Address
  996.  
  997.    Questions about this memo can also be directed to:
  998.  
  999.       Dave Rand
  1000.       Novell, Inc.
  1001.       2180 Fortune Drive
  1002.       San Jose, CA  95131
  1003.  
  1004.       +1 408 321-1259
  1005.  
  1006.       EMail: dave_rand@novell.com
  1007.  
  1008.  
  1009.  
  1010.  
  1011.  
  1012.  
  1013.  
  1014.  
  1015.  
  1016.  
  1017.  
  1018.  
  1019.  
  1020.  
  1021.  
  1022.  
  1023.  
  1024.  
  1025.  
  1026.  
  1027.  
  1028.  
  1029.  
  1030.  
  1031.  
  1032.  
  1033.  
  1034.  
  1035.  
  1036.  
  1037.  
  1038.  
  1039.  
  1040.  
  1041.  
  1042. Dave Rand                expires in six months                 [Page 18]
  1043. DRAFT                       PPP Compression                 October 1993
  1044.  
  1045.  
  1046.                            Table of Contents
  1047.  
  1048.  
  1049.      1.     Introduction ..........................................    1
  1050.  
  1051.      2.     A PPP Control Protocol (NCP) for Compression ..........    2
  1052.         2.1       Sending Compressed Datagrams ....................    2
  1053.  
  1054.      3.     CCP Configuration Options .............................    4
  1055.         3.1       Compression Type Negotiation Option (common) ....    5
  1056.         3.2       Compression Type Negotiation Option
  1057. (OUI/Proprietary) .................................................    7
  1058.  
  1059.      APPENDICES ...................................................    9
  1060.  
  1061.      A.     Common compression number identification ..............    9
  1062.  
  1063.      B.     Common compression algorithm definitions ..............   10
  1064.            B.1       Predictor algorithm ..........................   10
  1065.            B.2       Encapsulation for Predictor type 1 ...........   14
  1066.            B.3       Encapsulation for Predictor type 2 ...........   15
  1067.  
  1068.         C.     CCP Recommended Options ............................   16
  1069.  
  1070.         SECURITY CONSIDERATIONS ...................................   16
  1071.  
  1072.      REFERENCES ...................................................   16
  1073.  
  1074.      ACKNOWLEDGEMENTS .............................................   17
  1075.  
  1076.      CHAIR'S ADDRESS ..............................................   17
  1077.  
  1078.      AUTHOR'S ADDRESS .............................................   18
  1079.  
  1080.  
  1081.  
  1082.  
  1083.  
  1084.  
  1085.  
  1086.  
  1087.  
  1088.  
  1089.  
  1090.  
  1091.  
  1092.  
  1093.  
  1094.  
  1095.  
  1096.  
  1097.